package com.wc.算法提高课.D第四章_高级数据结构.可持久化数据结构.第K小数;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * @Author congge
 * @Date 2024/5/25 20:01
 * @description https://www.acwing.com/activity/content/problem/content/1718/
 */
public class Main {
    /**
     * 思路：存储每一个范围内的各个数的个数, 记录每一个插入的数的版本,
     * 他们的树的形状都是相同的 L , R ,   tr[R].l ~ tr[R].r 与 tr[L].l , tr[L].r 形状是相同的
     */
    static FastReader sc = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    static int N = 100010, M = 10010, idx = 1;
    static int[] a = new int[N], b = new int[N];
    static int[] root = new int[N];
    static Node[] tr = new Node[N * 4 + N * 17];
    static int n, m;

    public static void main(String[] args) {
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = b[i] = sc.nextInt();
        }
        Arrays.sort(b, 1, n + 1);
        b[0] = 1;
        for (int i = 2; i <= n; i++) {
            if (b[b[0]] != b[i]) {
                b[++b[0]] = b[i];
            }
        }
        tr[0] = new Node();
        root[0] = build(1, b[0]);
        for (int i = 1; i <= n; i++) {
            root[i] = insert(root[i - 1], 1, b[0], find(a[i]));
        }
        while (m-- > 0) {
            int l = sc.nextInt(), r = sc.nextInt(), k = sc.nextInt();
            out.println(b[query(root[r], root[l - 1], 1, b[0], k)]);
        }
        out.flush();
    }

    static int query(int q, int p, int l, int r, int k) {
        if (l == r) return r;
        int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
        int mid = l + r >> 1;
        if (cnt >= k) return query(tr[q].l, tr[p].l, l, mid, k);
        else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
    }

    static int build(int l, int r) {
        int p = idx++;
        tr[p] = new Node();
        if (l == r) return p;
        int mid = l + r >> 1;
        tr[p].l = build(l, mid);
        tr[p].r = build(mid + 1, r);
        return p;
    }

    static int insert(int p, int l, int r, int x) {
        int q = idx++;
        tr[q] = new Node();
        copyNode(p, q);
        if (l == r) {
            tr[q].cnt++;
            return q;
        }
        int mid = l + r >> 1;
        if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
        else tr[q].r = insert(tr[p].r, mid + 1, r, x);
        tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
        return q;
    }

    static void copyNode(int p, int q) {
        tr[q].l = tr[p].l;
        tr[q].r = tr[p].r;
        tr[q].cnt = tr[p].cnt;
    }

    static int find(int x) {
        int l = 1, r = b[0];
        while (l < r) {
            int mid = l + r >> 1;
            if (b[mid] >= x) r = mid;
            else l = mid + 1;
        }
        return l;
    }


    static class Node {
        // l与r存储的是孩子节点
        int l, r, cnt;
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    String nextLine() {
        String s = "";
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    // 是否由下一个
    boolean hasNext() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = br.readLine();
                if (line == null)
                    return false;
                st = new StringTokenizer(line);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }
}
